﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication
{
    /// <summary>
    /// 那些年我们用过的算法
    /// </summary>
    internal class Algorithm
    {
        #region [ 排序类 ]
        /** 排序分类
         * 稳定的
         *   冒泡排序（bubble sort） — O(n²)
         *   鸡尾酒排序(cocktail sort, 双向的冒泡排序) — O(n²)
         *   插入排序（insertion sort）— O(n²)
         *   桶排序（bucket sort）— O(n); 需要 O(k) 额外空间
         *   计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间
         *   合并排序（merge sort）— O(n log n); 需要 O(n) 额外空间
         *   原地合并排序 — O(n²)
         *   二叉排序树排序（Binary tree sort） — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
         *   鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
         *   基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间
         *   Gnome排序 — O(n²)
         *   图书馆排序 — O(n log n) with high probability, 需要 (1+ε)n 额外空间
         * 不稳定
         *   选择排序（selection sort）— O(n²)
         *   希尔排序（shell sort）— O(n log n) 如果使用最佳的现在版本
         *   组合排序 — O(n log n)
         *   堆排序（heapsort）— O(n log n)
         *   平滑排序 — O(n log n)
         *   快速排序（quicksort）— O(n log n) 期望时间, O(n²) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序
         *   Introsort — O(n log n)
         *   Patience sorting — O(n log n + k) 最坏情况时间，需要 额外的 O(n + k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）
         */
        #region 冒泡排序 O(n²)
        /// <summary>
        /// 冒泡排序
        /// <para>平均时间复杂度O(n²)</para>	
        /// <para>最差空间复杂度总共O(n)，需要辅助空间O(1)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void BubbleSort(int[] array)
        {
            /**
             * 冒泡排序算法的运作如下：
             * 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
             * 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
             * 3、针对所有的元素重复以上的步骤，除了最后一个。
             * 3、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
             */
            int temp;
            for (int i =0; i<array.Length - 1; i++)       /*外循环控制排序趟数，n个数排n-1趟*/
            {
                for (int j = 0; j < array.Length-i-1;j++) /*内循环每趟比较的次数，第j趟比较n-i次*/
                {
                    if (array[j + 1] < array[j])           /*相邻元素比较，逆序则交换*/
                    {
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
        #endregion
        #region 插入排序 O(n²)
        /// <summary>
        /// 插入排序
        /// <para>平均时间复杂度O(n²)</para>	
        /// <para>最差空间复杂度总共O(n)，需要辅助空间O(1)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void InsertionSort(int[] array)
        {
            /**
             * 插入排序都采用in-place在数组上实现。具体算法描述如下：
             * 1、从第一个元素开始，该元素可以认为已经被排序
             * 2、取出下一个元素，在已经排序的元素序列中从后向前扫描
             * 3、如果该元素（已排序）大于新元素，将该元素移到下一位置
             * 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
             * 5、将新元素插入到该位置后
             * 6、重复步骤2~5
             */
            int temp,j;
            for (int i = 1; i < array.Length; i++)
            {
                temp = array[i];
                j = i;
                while (j > 0 && array[j - 1] > temp)
                {
                    array[j] = array[j - 1];
                    --j;
                }
                array[j] = temp;
            }
        }
        #endregion
        #region 选择排序 O(n²)
        /// <summary>
        /// 选择排序
        /// <para>平均时间复杂度O(n²)</para>	
        /// <para>最差空间复杂度总共O(n)，需要辅助空间O(1)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void SelectionSort(int[] array)
        {
            /**
             * 工作原理如下:
             * 1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
             * 2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
             * 3、以此类推，直到所有元素均排序完毕
             */
            int min, temp;
            for (int i = 0; i < array.Length - 1; ++i)
            {
                min = i;
                for (int j = i + 1; j < array.Length; ++j)
                {
                    if (array[j] < array[min])
                        min = j;
                }
                temp = array[min];
                array[min] = array[i];
                array[i] = temp;
            }    

        }
        #endregion
        #region 归并排序 O(nlogn)
        /// <summary>
        /// 归并排序
        /// <para>平均时间复杂度O(nlogn)</para>	
        /// <para>最差空间复杂度总共O(n)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void MergeSort(int[] array)
        {
            /**
             * 归并操作的过程如下：
             * 1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
             * 2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
             * 3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
             * 4、重复步骤3直到某一指针达到序列尾
             * 5、将另一序列剩下的所有元素直接复制到合并序列尾
             */
            if (array.Length <= 1) return;
            int middle = array.Length / 2;
            int[] left = new int[middle],
                right = new int[array.Length - middle];
            int i = 0, j = 0;
            foreach (int x in array)
            {
                if (i < middle)
                {
                    left[i++] = x;
                }
                else
                {
                    right[j++] = x;
                }
            }
            MergeSort(left); //递归左数组
            MergeSort(right);//递归右数组
            Merge(left, right,ref array);
        }
        /// <summary>
        /// 归并排序之并:排序在这一步
        /// </summary>
        /// <param name="left">左数组</param>
        /// <param name="right">右数组</param>
        /// <param name="result">合并前的数组</param>
        /// <returns></returns>
        private static void Merge(int[] left, int[] right,ref int[] result)
        {
            int i = 0, j = 0, k = 0;
            while (i < left.Length && j < right.Length)
            {
                if (left[i] < right[j])
                {
                    result[k++] = left[i++];
                }
                else
                {
                    result[k++] = right[j++];
                }
            }
            while (i < left.Length)
            {
                result[k++] = left[i++];
            }
            while (j < right.Length)
            {
                result[k++] = right[j++];
            }
        }
        #endregion
        #region 堆排序   O(nlogn)
        /// <summary>
        /// 堆排序
        /// <para>平均时间复杂度O(nlogn)</para>	
        /// <para>最差空间复杂度总共O(n)，需要辅助空间O(1)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void HeapSort(int[] array)
        {
            /**
             * 在堆的数据结构中，堆中的最大值总是位于根节点。堆中定义以下几种操作：
             * 1、最大堆调整（Max_Heapify）：将堆的末端子结点作调整，使得子结点永远小于父结点
             * 2、创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
             * 3、堆排序（HeapSort）：移除位在第一个数据的根结点，并做最大堆调整的递归运算
             */
            BuildMaxHeap(array);    //创建大顶推（初始状态看做：整体无序）
            int temp;
            for (int i = array.Length - 1; i > 0; i--)
            {
                temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                MaxHeapify(array, 0, i); //重新将无序区调整为大顶堆
            }
        }

        /// <summary>
        /// 创建最大堆（根节点大于左右子节点）
        /// </summary>
        /// <param name="array"></param>
        private static void BuildMaxHeap(int[] array)
        {
            //根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点
            for (int i = array.Length / 2 - 1; i >= 0; i--) //从最底层的最后一个根节点开始进行大顶推的调整
            {
                MaxHeapify(array, i, array.Length); //调整大顶堆
            }
        }

        /// <summary>
        /// 最大堆调整
        /// </summary>
        /// <param name="array">待调整的数组</param>
        /// <param name="index">待调整元素在数组中的位置（即：根节点）</param>
        /// <param name="heapSize">堆中所有元素的个数</param>
        private static void MaxHeapify(int[] array, int index, int heapSize)
        {
            int left = 2 * index + 1,    //左子节点在数组中的位置
               right = 2 * index + 2,   //右子节点在数组中的位置
               large = index;   //记录此根节点、左子节点、右子节点 三者中最大值的位置

            if (left < heapSize && array[left] > array[large])  //与左子节点进行比较
            {
                large = left;
            }
            if (right < heapSize && array[right] > array[large])    //与右子节点进行比较
            {
                large = right;
            }
            if (index != large)  //如果 index != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）
            {
                int temp = array[index];
                array[index] = array[large];
                array[large] = temp;                //将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）
                MaxHeapify(array, large, heapSize); //以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整
            }
        }
        #endregion
        #region 快速排序 O(nlogn)
        /// <summary>
        /// 快速排序
        /// <para>平均时间复杂度O(nlogn)</para>	
        /// <para>空间复杂度一般版本O(n)，In-place O(logn)</para>
        /// </summary>
        /// <param name="array"></param>
        public static void QuickSort(int[] array)
        {
            /**
             * 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
             * 步骤为：
             * 1、从数列中挑出一个元素，称为 "基准"（pivot），
             * 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
             *    在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
             * 3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
             */
            QuickSort(array, 0, array.Length - 1);
        }

        private static void QuickSort(int[] array, int left, int right)
        {
            if (left < right)
            {
                int middle = array[(left + right) / 2],
                    i = left - 1,
                    j = right + 1,
                    temp;
                while (true)
                {
                    while (array[++i] < middle) ;
                    while (array[--j] > middle) ;
                    if (i >= j) break;
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
                QuickSort(array, left, i - 1);
                QuickSort(array, j + 1, right);
            }
        }
        #endregion
        #region 希尔排序 O(n^1.25)
        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="array"></param>
        public static void ShellSort(int[] array)
        {
            /**
             * 
             */
            int i, j, temp;
            for (int step = array.Length / 2; step > 0; step /= 2)
            {
                for (i = step; i < array.Length; i++)
                {
                    temp = array[i];
                    j = i - step;
                    while (j >= 0 && array[j] > temp)
                    {
                        array[j + step] = array[j];
                        j -= step;
                    }
                    /*
                    for (j = i - step; j >= 0 && array[j] > temp; j -= step)
                    {
                        array[j + step] = array[j];
                    }*/
                    array[j + step] = temp;
                }
            }
        }
        #endregion
        #region 基数排序 O(n)
        /// <summary>
        /// 基数排序
        /// </summary>
        /// <param name="array"></param>
        public static void RadixSort(int[] array)
        {

        }
        #endregion
        #endregion
    }
}
